class Solution2 {
    public int posIndex;
    /**
     * 10. 根据一棵树的中序遍历与后序遍历构造二叉树
     * https://leetcode.cn/problems/construct-binary-tree-from-inorder-and-postorder-traversal/
     */
        static class TreeNode {
            public int val;
            public TreeNode left;
            public TreeNode right;

            public TreeNode(int val) {
                this.val = val;
            }
        }
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        posIndex = postorder.length - 1;
        return buildTreeChilde(postorder,inorder,0,inorder.length - 1);
    }
    private TreeNode buildTreeChilde(int[] inorder, int[] postorder,int inbegin ,int inend) {
        if(inbegin > inend) {
            return null;
        }
        TreeNode root = new TreeNode(inorder[posIndex]);
        int rootIndex = findInDexRoot(postorder,inorder[posIndex],inbegin,inend);
        if(rootIndex == -1) {
            return null;
        }
        posIndex--;
        root.right = buildTreeChilde(inorder,postorder,rootIndex + 1,inend);
        root.left = buildTreeChilde(inorder,postorder,inbegin,rootIndex - 1);
        return root;
    }

    private int findInDexRoot(int[] postorder,int key,int inbegin,int inend) {
        for(int i = inbegin ; i <= inend;i++) {
            if(key == postorder[i]) {
                return i;
            }
        }
        return -1;
    }
}